import com.sun.source.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;

    }

    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null) return;

        System.out.print(root.val + " ");

        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null) return;

        inOrder(root.left);

        System.out.print(root.val + " ");

        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(TreeNode root){
        //DHEBFGCA
        if(root == null) return;

        postOrder(root.left);
        postOrder(root.right);

        System.out.print(root.val + " ");
    }

    //获取当前二叉树节点的个数
    public int nodeSize;
    public void getNodeSize(TreeNode root){
        if(root == null) return ;
        nodeSize++;
        getNodeSize(root.left);
        getNodeSize(root.right);
    }

    public int getNodeSize2(TreeNode root){
        if(root == null) return 0;
        return getNodeSize2(root.left) +
                getNodeSize2(root.right) + 1;
    }

    public int LeafConut;
    //获取当前二叉树叶子节点的个数
    public void getLeafNodeCount(TreeNode root){
        if(root == null) return ;
        if(root.left == null && root.right == null){
            LeafConut++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }

    public int getLeafNodeCount2(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount2(root.left) +
                getLeafNodeCount2(root.right);

    }

    //求第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null) return 0;
        if(k == 1) return 1;
        return getKLevelNodeCount(root.left,k - 1) +
                getKLevelNodeCount(root.right,k - 1);
    }


    //二叉树的高度
    public int getHigh(TreeNode root){
        if(root == null) return 0;
        int leftHigh = getHigh(root.left);
        int rightHigh = getHigh(root.right);

//        return Math.max(leftHigh, rightHigh) + 1;
        return leftHigh > rightHigh ? leftHigh + 1: rightHigh + 1;
    }

    //检测值为 value 的元素是否存在
    public TreeNode find(TreeNode root,char key){
        if(root == null) return null;
        if(root.val == key) return root;
        TreeNode leftResult = find(root.left,key);
        if(leftResult != null){
            return leftResult;
        }
        TreeNode rightResult = find(root.right,key);
        if(rightResult != null){
            return rightResult;
        }
        return null;
    }


    public boolean isSameTree(TreeNode p,TreeNode q){
        //一个为空，一个不为空
        if(p == null && q !=null || q == null && p !=null){
            return false;
        }
        //此时两树都不为空或者都为空
        if(p == null && q == null) return true;
        if(p.val != q.val) return false;

        return isSameTree(p.left,q.left)
                && isSameTree(p.right,q.right);
    }

    //判断一棵树是不是另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null){
            return true;
        }
        if(root == subRoot){
            isSubtree(root.left,subRoot.left);
            isSubtree(root.right,subRoot.right);
        }
        return isSubtree(root.left,subRoot)
                && isSubtree(root.right,subRoot);
    }

    //反转树
    public TreeNode invertTree(TreeNode root){
        if(root == null) return null;
        TreeNode tmp;
        tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //判断是否为平衡二叉树
    //方法一：
    //时间复杂度为 O(N^2)
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        int left = getHigh2(root.left);
        int right = getHigh2(root.right);

        return Math.abs(left - right) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public int getHigh2(TreeNode root){
        if(root == null) return 0;
        int leftHigh = getHigh2(root.left);
        int rightHigh = getHigh2(root.right);

        return Math.max(leftHigh,rightHigh) + 1;
    }

    //方法二：
    //时间复杂度为 O(N)
    public boolean isBalanced2(TreeNode root) {
        if(root == null) return true;

        return getHigh3(root) >= 0;
    }

    public int getHigh3(TreeNode root){
        if(root == null) return 0;
        int leftHigh = getHigh2(root.left);
        if(leftHigh < 0){
            return -1;
        }
        int rightHigh = getHigh2(root.right);
        if(leftHigh >= 0 && rightHigh >= 0 && Math.abs(leftHigh - rightHigh) <= 1){
            return Math.max(leftHigh,rightHigh) + 1;
        }else{
            return -1;
        }
    }

    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return false;
        return cmp(root.left,root.right);
    }

    public boolean cmp(TreeNode leftTree,TreeNode rightTree){
        if(leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null) return false;
        if(leftTree == null && rightTree == null) return true;
        if(leftTree.val != rightTree.val){
            return false;
        }
        return cmp(leftTree.left,rightTree.right) &&
                cmp(leftTree.right,rightTree.right);
    }

    //层序遍历
    public void levelOrder(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

    //层序遍历二：
//    public List<List<Integer>> levelOrder2(TreeNode root) {
//        List<List<Integer>> ret = new ArrayList<>();
//        if(root == null) return ret;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while(!queue.isEmpty()){
//            List<Integer> tmpList = new LinkedList<>();
//            int size = queue.size();
//            while(size != 0){
//                TreeNode cur = queue.poll();
//                size--;
//                // System.out.print(cur.val + " ");
//                tmpList.add(cur.val);
//                if(cur.left != null){
//                    queue.offer(cur.left);
//                }
//                if(cur.right != null){
//                    queue.offer(cur.right);
//                }
//            }
//            ret.add(tmpList);
//        }
//        return ret;
//    }
}
